package dynamicProgramming.bagQuestion;

import binaryTree.LayerOrderTraversal.Basic429;

import java.util.Arrays;

public class Bag01 {

    //  在 n 个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为
    //�
    //�
    //A
    //i
    //​
    //
    //（每个物品只能选择一次且物品大小均为正整数）

    public int backPack(int m, int[] a) {
        // write your code here
        return  process(a,0,m);
    }

    public  int   process(int[] a,int index, int rest){
        if (index==a.length){
            return  0;
        }
  //TODO:2024/1/23 装不进去的时候
        int p1=process(a,index+1,rest);
        int p2=0;
        //TODO:2024/1/23 装进去的时候
        if (rest>=a[index]){
            p2=a[index]+process(a,index+1,rest-a[index]);
        }
        return   Math.max(p1,p2);
    }




    //TODO:2024/1/23 第二种方法 带有缓存的方法  带有记忆的搜索方法
    int[][] dp;
    public int backPack1(int m, int[] a) {
        //TODO:2024/1/23  dp【i】【j】代表的含义是
        // 从a数组下标i开始的在容量为j的背包中能装入的最大质量
        dp=new int[a.length+1][m+1];
        for (int i = 0; i < dp.length; i++) {
            Arrays.fill(dp[i],-1);
        }
        return   process1(a,0,m);
    }

    public  int   process1(int[] a,int index, int rest) {
     if (index==a.length){
         return 0;
     }
     if (dp[index][rest]!=-1){
         return  dp[index][rest];
     }
        int p1=process1(a,index+1,rest);
        int p2=0;
        //TODO:2024/1/23 装进去的时候
        if (rest>=a[index]){
            p2=a[index]+process1(a,index+1,rest-a[index]);
        }
        dp[index][rest]=Math.max(p1,p2);
        return   Math.max(p1,p2);
    }



    int[][] dp1;
    public int backPack2(int m, int[] a) {
        dp1=new int[a.length+1][m+1];
        for (int index = a.length-1; index>=0; index--) {
            for (int rest = 0; rest <=m; rest++) {
                int p1=dp1[index+1][rest];
                int p2=0;
                //TODO:2024/1/23 装进去的时候
                if (rest>=a[index]){
                    p2=a[index]+dp1[index+1][rest-a[index]];
                }
                dp1[index][rest]=Math.max(p1,p2);

            }
        }
        return  dp1[0][m];
    }

//TODO:2024/1/24  我自己写出来的
    public int backPack3(int m, int[] a) {
        int[][]dp=new int[a.length+1][m+1];
        for (int index = 1; index<=a.length; index++) {
            for (int rest = 1; rest <=m; rest++) {
               if (a[index-1]>rest){
                   dp[index][rest]=dp[index-1][rest];
               }else {
                   dp[index][rest]=Math.max(a[index-1]+dp[index-1][rest-a[index-1]],dp[index-1][rest]);
               }
            }
        }
        return  dp[a.length][m];
    }


    public static void main(String[] args) {

        int[] arr={3,4,8,5};
        Bag01 bag01 = new Bag01();
        int i = bag01.backPack3(10, arr);
        System.out.println(i);
    }







}
